import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * Created by zhourh on 2018/6/15.
 *
 * 给定一个所有节点为非负值的二叉搜索树，求树中任意两节点的差的绝对值的最小值。

 示例 :

 输入:

 1
 \
 3
 /
 2

 输出:
 1

 解释:
 最小绝对差为1，其中 2 和 1 的差的绝对值为 1（或者 2 和 3）。

 */
public class MinimumAbsoluteDifferenceInBST {

    public static void main(String[] args) {
        TreeNode node = new TreeNode(1);
        node.right = new TreeNode(3);
        node.right.left = new TreeNode(2);

        System.out.println(new MinimumAbsoluteDifferenceInBST().getMinimumDifference(node));
    }

    public int getMinimumDifference(TreeNode root) {
        if (root == null) {
            return 0;
        }

        List<Integer> nums = new ArrayList<>();
        dfs(nums, root);
        Collections.sort(nums);
        int minAbs = Integer.MAX_VALUE;
        for (int i = 0; i < nums.size() - 1; i++ ) {
            int abs = nums.get(i + 1) - nums.get(i);
            minAbs = Math.min(minAbs, abs);
        }

        return minAbs;

    }

    public void dfs(List<Integer> list, TreeNode node) {
        list.add(node.val);

        if (node.left != null) {
            dfs(list, node.left);
        }

        if (node.right != null) {
            dfs(list, node.right);
        }
    }
}
